//原文链接
//https://blog.csdn.net/ITSOK_123/article/details/124526013

//递归（O(N),O(N)）
void postTraversal(TreeNode* root,vector<int>& vec){
        if(root == nullptr) return;
        postTraversal(root->left,vec);
        postTraversal(root->right,vec);
        vec.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postTraversal(root,res);
        return res;
    }

//类前序迭代（O(N),O(N)）

vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if(root == nullptr) return res;
        st.push(root);

        while(!st.empty()){
            TreeNode* node = st.top();
            res.push_back(node->val);
            st.pop();
            //左子树根节点入栈
            if(node->left != nullptr) st.push(node->left);
            //右子树根节点入栈
            if(node->right != nullptr) st.push(node->right);
        }
        //vector倒置
        reverse(res.begin(),res.end());
        return res;
    }

//直接迭代（O(N),O(N)）
vector<int> postorderTraversal(TreeNode* root) {
        //按照左右根的顺序遍历
        //但是要进行访问记录
        vector<int> res;
        stack<TreeNode*> st;
        if(root == nullptr) return res;
        // 根节点入栈
        st.push(root);
        // 记录最后一次出栈的元素，防止重复遍历节点的左右子树
        TreeNode *lastN = root;

        while(!st.empty()){
            TreeNode* node = st.top();
            //左右子树
            //有左子树就先遍历左子树
            if(node->left && node->left != lastN && node->right != lastN ) st.push(node->left);
            //只有左子树为空或者左子树已经遍历过才会遍历右子树
            else if(node->right && node->right != lastN) st.push(node->right);
            // 左右子树均已经遍历过则进行根节点处理
            else{
                //当前节点是叶节点或者其左右子树已经处理过
                res.emplace_back(node->val);
                st.pop();
                lastN = node;
            }
        }
        return res;
    }
